package com.zdp.leetcodeMiddle;
/*
* 题目描述：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
* 示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 最长重复子数组 {
    public static void main(String[] args) {
        最长重复子数组 demo = new 最长重复子数组();
        String s = "321";
        String ss = "32147";
        System.out.println(ss.indexOf(s));
        System.out.println(demo.findLength(new int[]{70,39,25,40,7}, new int[]{52,20,67,5,31}));
    }
    /*
    * 利用滑动窗口
    * */
    public int findLength(int[] A, int[] B) {
        //利用滑动窗口,A固定,B滑过A
        //B固定,A滑过B,再比较的过程中记录匹配的长度
        int alength = A.length;
        int blength = B.length;
        //先滑A,B固定
        int result = 0;
        for(int i=0;i<A.length;i++){
            //先得出滑动窗口的长度,有长到短
            //可以在图上画一下,一开始A和B头头对齐,那么滑动窗口的长度就是长度较小的那个数组
            //这个窗口的大小,其实是两个数组对齐的元素的数量
            int winlenth = Math.min(blength,alength-i); //B固定,A滑动,所以B的长度不动,A的长度因为滑动会变化(i为滑出去多少个)
            int maxlen = getMax(A,B,i,0,winlenth); //B固定,A滑动,所以B都是从0开始,A是左滑,所以以i开始
            result = Math.max(result,maxlen);
        }
        //现在滑B,为了把所有的情况都确认一遍
        for(int i=0;i<B.length;i++){
            int winlenth = Math.min(alength,blength-i);
            int maxlen = getMax(A,B,0,i,winlenth);
            result = Math.max(result,maxlen);
        }
        return result;
    }

    //apos不动,bpos动
    public int getMax(int[]A,int[]B,int apos,int bpos,int winlen){
        int count = 0;
        int max = 0;
        for(int i=0;i<winlen;i++){
            if(A[apos+i]==B[bpos+i]){
                count++;
            }else{
                count = 0; //不相等等于0,防止count的值影响到后面的计算
            }
            max = Math.max(count,max);
        }
        return max;
    }
}
